/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/digit-counts
   @Language: C++
   @Datetime: 16-02-09 05:47
   */

// Method 1, Time O(nlogn)
class Solution {
public:
    /*
     * param k : As description.
     * param n : As description.
     * return: How many k's between 0 and n.
     */
    int digitCounts(int k, int n) {
        // write your code here
        int cnt = k==0;
        for (int i=1; i<=n; ++i){
            for (int num=i; num; num/=10)
                cnt += (num%10==k);
        }
        return cnt;
    }
};

// Method 2, Time O(logn)
class Solution {
public:
	/*
	 * param k : As description.
	 * param n : As description.
	 * return: How many k's between 0 and n.
	 * Tip : statistics k appear at each bit
	 */
	int digitCounts(int k, int n) {
		// write your code here
		if(!k && !n) return 1;
		int cnt=0, high=n, bit, mod, factor=1;
		for(; high; factor*=10){
			bit = high%10;
			high /=10;
			mod = n%factor;
			// k appear at bit in range [K000,XXXXXXB000]
			cnt += (high+(k<bit))*factor;
			// k==0, K000 has no k in bit, except K000==0.
			if (k==0 && factor>1) cnt -= factor;
			// bit==k, k appear in range [XXXXXB000,XXXXXBXXX]
			if (k==bit) cnt += mod+1;
		}
		return cnt;
	}
};
